//
// Created by francklinson on 2021/7/5.
//
//给定一个化学式formula（作为字符串），返回每种原子的数量。
//
//原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。
//
//如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。
//
//两个化学式连在一起是新的化学式。例如H2O2He3Mg4 也是化学式。
//
//一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。
//
//给定一个化学式formula ，返回所有原子的数量。格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

#include <string>
#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;


class Solution {
public:
    string countOfAtoms(string formula) {
        int i = 0, n = formula.length();

        // 提取原子 一定是一个大写字母+若干可能的小写字母
        auto parseAtom = [&]() -> string {
            string atom;
            atom += formula[i++]; // 扫描首字母
            while (i < n && islower(formula[i])) {
                atom += formula[i++]; // 扫描首字母后的小写字母
            }
            return atom;
        };
        // 提取数量
        auto parseNum = [&]() -> int {
            if (i == n || !isdigit(formula[i])) {
                return 1; // 不是数字，视作 1
            }
            int num = 0;
            while (i < n && isdigit(formula[i])) {
                num = num * 10 + int(formula[i++] - '0'); // 扫描数字
            }
            return num;
        };
        // 栈 存放hash表
        stack<unordered_map<string, int>> stk;
        // 初始存入一个空的hash表
        stk.push({});
        while (i < n) {
            char ch = formula[i];
            if (ch == '(') { // 遇到左括号

                i++;
                stk.push({}); // 将一个空的哈希表压入栈中，准备统计括号内的原子数量
            } else if (ch == ')') {  // 遇到右括号
                i++;
                int num = parseNum(); // 括号右侧数字
                auto atomNum = stk.top();
                stk.pop(); // 弹出括号内的原子数量
                for (auto &x : atomNum) {
                    stk.top()[x.first] += x.second * num; // 将括号内的原子数量乘上 num，加到上一层的原子数量中
                }
            } else {
                string atom = parseAtom();
                int num = parseNum();
                stk.top()[atom] += num; // 统计原子数量
            }
        }
        // 最后结果全部在栈顶
        auto &atomNum = stk.top();
        vector<pair<string, int>> pairs;
        pairs.reserve(atomNum.size());
        for (auto &x : atomNum) {
            pairs.emplace_back(x.first, x.second);
        }
        // 排序
        sort(pairs.begin(), pairs.end());
        // 返回字符串
        string ans;
        for (auto &p : pairs) {
            ans += p.first;
            if (p.second > 1) {
                ans += to_string(p.second);
            }
        }
        return ans;
    }
};


int main() {
    Solution sol;
//    cout << sol.countOfAtoms("H2O") << endl;
    cout << sol.countOfAtoms("K4(ON(SO3)2)2") << endl;
    return 0;
}